#include <linux/memblock.h>
#include <linux/minmax.h>
#include <asm/page.h>
#include <linux/limits.h>

#define __for_each_mem_range(i, type_a, type_b, nid, flags,      \
                             p_start, p_end, p_nid)              \
    for (i = 0, __next_mem_range(&i, nid, flags, type_a, type_b, \
                                 p_start, p_end, p_nid);         \
         i != (u64)ULLONG_MAX;                                   \
         __next_mem_range(&i, nid, flags, type_a, type_b,        \
                          p_start, p_end, p_nid))

#define for_each_free_mem_range(i, nid, flags, p_start, p_end, p_nid) \
    __for_each_mem_range(i, &memblock.memory, &memblock.reserved,     \
                         nid, flags, p_start, p_end, p_nid)

static bool should_skip_region(struct memblock_type *type,
                               struct memblock_region *m,
                               int nid, int flags)
{
    return false;
}

void __next_mem_range(u64 *idx, int nid, enum memblock_flags flags,
                      struct memblock_type *type_a,
                      struct memblock_type *type_b, phys_addr_t *out_start,
                      phys_addr_t *out_end, int *out_nid)
{
    int idx_a = *idx & 0xffffffff;
    int idx_b = *idx >> 32;

    for (; idx_a < type_a->cnt; idx_a++)
    {
        struct memblock_region *m = &type_a->regions[idx_a];

        phys_addr_t m_start = m->base;
        phys_addr_t m_end = m->base + m->size;
        int m_nid = memblock_get_region_node(m);

        if (should_skip_region(type_a, m, nid, flags))
            continue;

        if (!type_b)
        {
            if (out_start)
                *out_start = m_start;
            if (out_end)
                *out_end = m_end;
            if (out_nid)
                *out_nid = m_nid;
            idx_a++;
            *idx = (u32)idx_a | (u64)idx_b << 32;
            return;
        }

        /* scan areas before each reservation */
        for (; idx_b < type_b->cnt + 1; idx_b++)
        {
            struct memblock_region *r;
            phys_addr_t r_start;
            phys_addr_t r_end;

            r = &type_b->regions[idx_b];
            r_start = idx_b ? r[-1].base + r[-1].size : 0;
            r_end = idx_b < type_b->cnt ? r->base : PHYS_ADDR_MAX;

            /*
             * if idx_b advanced past idx_a,
             * break out to advance idx_a
             */
            if (r_start >= m_end)
                break;
            /* if the two regions intersect, we're done */
            if (m_start < r_end)
            {
                if (out_start)
                    *out_start =
                        max(m_start, r_start);
                if (out_end)
                    *out_end = min(m_end, r_end);
                if (out_nid)
                    *out_nid = m_nid;
                /*
                 * The region which ends first is
                 * advanced for the next iteration.
                 */
                if (m_end <= r_end)
                    idx_a++;
                else
                    idx_b++;
                *idx = (u32)idx_a | (u64)idx_b << 32;
                return;
            }
        }
    }

    /* signal end of iteration */
    *idx = ULLONG_MAX;
}

static phys_addr_t __memblock_find_range_bottom_up(phys_addr_t start, phys_addr_t end,
                                                   phys_addr_t size, phys_addr_t align, int nid,
                                                   enum memblock_flags flags)
{
    phys_addr_t this_start, this_end, cand;
    phys_addr_t found = 0;
    u64 i;

    for_each_free_mem_range(i, nid, flags, &this_start, &this_end, NULL)
    {
        this_start = clamp(this_start, start, end);
        this_end = clamp(this_end, start, end);

        cand = round_up(this_start, align);
        if (cand < this_end && this_end - cand >= size)
        {
            found = cand;
            break;
        }
    }

    return found;
}

static phys_addr_t memblock_find_in_range_node(phys_addr_t size,
                                               phys_addr_t align, phys_addr_t start,
                                               phys_addr_t end, int nid,
                                               enum memblock_flags flags)
{
    phys_addr_t found;

    /* pump up @end */
    if (end == MEMBLOCK_ALLOC_ACCESSIBLE ||
        end == MEMBLOCK_ALLOC_NOLEAKTRACE)
        end = memblock.current_limit;

    /* avoid allocating the first page */
    start = max_t(phys_addr_t, start, PAGE_SIZE);
    end = max(start, end);

    found = __memblock_find_range_bottom_up(start, end, size, align,
                                            nid, flags);

    return found;
}
